Integrality gaps for strengthened LP relaxations of Capacitated and Lower-Bounded Facility Location

摘要

The metric uncapacitated facility location problem (UFL) enjoys a specialstature in approximation algorithms as a testbed for various techniques. Twogeneralizations of UFL are capacitated facility location (CFL) andlower-bounded facility location (LBFL). In the former, every facility has acapacity which is the maximum demand that can be assigned to it, while in thelatter, every open facility is required to serve a given minimum amount ofdemand. Both CFL and LBFL are approximable within a constant factor but theirrespective natural LP relaxations have an unbounded integrality gap. Accordingto Shmoys and Williamson, the existence of a relaxation-based algorithm for CFLis one of the top 10 open problems in approximation algorithms. In this paper we give the first results on this problem. We providesubstantial evidence against the existence of a good LP relaxation for CFL byshowing unbounded integrality gaps for two families of strengthenedformulations. The first family we consider is the hierarchy of LPs resulting from repeatedapplications of the lift-and-project Lov\'{a}sz-Schrijver procedure startingfrom the standard relaxation. We show that the LP relaxation for CFL resultingafter $\Omega(n)$ rounds, where $n$ is the number of facilities in theinstance, has unbounded integrality gap. Note that the Lov\'{a}sz-Schrijverprocedure is known to yield an exact formulation for CFL in at most $n$ rounds. We also introduce the family of proper relaxations which generalizes to itslogical extreme the classic star relaxation, an equivalent form of the naturalLP. We characterize the integrality gap of proper relaxations for both LBFL andCFL and show a threshold phenomenon under which it decreases from unbounded to1.